This invention relates to the field of binary adders and to a new signal selection adder architecture which improves both propagation time and adder fabrication space or circuit area requirements for such adders.
Binary addition improvements have been the subject of intensive investigation especially in the period since the commercial advent of the digital computer in the 1940's and 1950's. A principal stimulus for this effort arises from the limitation in computation speed created by the time for accomplishing addition--the most basic and often used of the computer arithmetic operations. In such addition moreover a limiting consideration is the time for rippling of the carry signal through the adder stages.
The time to compute a sum has therefore received attention because it carries such significant weight within any computer system. In even the most fundamental microprocessor chip there are, for example, numerous adders, incrementers, comparators, and in some current architectures, multipliers, all of which employ addition. Also, computer Arithmetic Logic Units perform addition on data, and a program counter must be incremented or modified--frequently through the use of complement addition. Most of these addition inclusive units are, of even further significance, located on the critical path of a system. The achievable clock period and the overall computation speed of a system architecture is therefore often directly related to the time required to perform addition.
Reducing the time to perform addition, however, typically requires an increase in circuit area, as the increase in performance is often achieved through the use of non-minimized and/or redundant circuits. This results in faster but larger adder circuits. The area-time product may therefore be used to measure the effectiveness of an architecture by contrasting the trade-off between increased performance and increased circuit area. Using an adder that is fast or faster than current methods, and also has a lower area-time product, thereby results in a system that is significantly improved over the state of the art.
The basis for adder limitations in a system arises from the inherent nature of the binary number system and from the fact that in this system a final sum bit is data dependent upon the value of all addend and augend bits supplied to the adder down to the lowest or least significant bit. This situation is discussed, for example, in the article "High-Speed Arithmetic In Binary Computers" written by O. L. MacSoley and published in the proceedings of The Institute of Radio Engineers pages 67-91 in January 1961.
Several methods have been developed to reduce the time required for computing the carry signal contribution to the most significant bit position of a sum. Some of these methods are, for example, known by the names of carry-look ahead, Manchester carry chain, and carry-select. Other methods such as carry save, Wallace trees, and Dadda trees have application in multipliers but are not relevant where addition only is considered. For the methodologies that are relevant , in addition to the time to produce a complete sum, an important factor to be considered is the average number of gates per bit slice required to implement the adder architecture. As circuit area is directly related to the gate count, it is common to use the gate count as representative of area. For the area-time metric, a similarly valid metric for comparison of these circuits is a gate-time product.
The carry-select adder from this group provides a convenient starting point for discussion of the present invention. The carry select adder has been described in numerous parts of the technical literature. Included in these descriptions is the article "Carry-Select Adder" authored by O. J. Bedrij appearing in the June 1962 issue of the Institute Of The Radio Engineers Publication "Transactions on Electronic Computers" commencing at page 340. The carry-select adder is also described in text books including the text "Computer Arithmetic Principles-Architecture and Design" authored by Kai Hwang, and published by John Wiley and Sons 1979, especially commencing at page 81. FIGS. 3.7 and 3.8 located on pages 82 and 83 of the Hwang text are particularly descriptive of a carry-select adder. Both the Bedrij and Hwang publications are hereby incorporated by reference herein.
The carry-select adder provides a trade off between optimal area and optimal processing time in an adder. The carry-select adder is in fact of the order of n, the number of bits, in area requirement and of the order of the square root of n in time delay generation. An underlying principle of carry-select addition is to break the adder up into stages in which the sum is computed for both the case of a zero and a one carry input. Then when the carry from the previous stage is computed and ready, the correct sum output is chosen along with the correct carry output for the stage. After the initial stage's time delay, proper sizing of the number of bits in each successive stage increases the time by only one gate delay with this delay coming from multiplexing of the correct carry from one stage to the next. The present invention can be considered to evolve from the carry-select adder but significantly improves upon several aspects of this carry-select adder.
The patent art also shows examples of the carry-select and related adders which are of general interest with respect to the present invention. Included in this patent art is the U.S. Pat. Nos. 4,525,797 of K. N. Holden; 4,704,701 of M. Mazin et al.; and 4,764,888 also of K. N. Holden et al. all of which are concerned with variations of the carry-select adder and U.S. Pat. No. 4,811,272 of G. M. Wolrich which is concerned with an improved floating point operation in an arithmetic logic unit. Although each of these prior patents relates to an improvement in the structure of a conditional adder none includes the circuit area conserving and optimized relationship between addend and augend bit count and propagation delay offered by the adder of the present invention.